/*
 * @lc app=leetcode id=50 lang=cpp
 *
 * [50] Pow(x, n)
 */
class Solution {
public:
    double myPow(double x, int n) {

        long nl = n;
        bool inverse = false;
        if (n == 0) {
            return 1;
        } else if (n < 0) {
            nl = -nl;
            inverse = true;
        }

        double v = myTmpPow(x, nl);
        v = inverse ? 1/v : v;
        return v;
    }

    double myTmpPow(double x, long n) {
        if (n == 1) {
            return x;
        } else if (n == 0) {
            return 1;
        } 

        double tmp = myPow(x, n/2);
        double ret = tmp*tmp;
        if (n & 0x01) {
            ret *= x;
        }
        return ret; 
    }
};

